Databases no longer just store integers and strings. Databases continue to expand in interesting directions. One direction involves storing three dimensional data types. Conventional database systems may have provided limited support, if any, for query processing on three dimensional surfaces. For example, conventional systems may have provided little, if any, support for identifying whether two surfaces intersect with other. Similarly, conventional systems may have provided little, if any, support, for identifying whether two solids intersect each other.
In computational geometry, detecting whether two geometries intersect and computing where the intersection occurs are fundamental tasks. Geometric intersection queries are associated with applications including map overlay in geographic information systems, component layout in very large scale integration (VLSI) design, motion and path planning in robotics, collision detection, and so on.